"""
    迷宫问题
    规定上下左右四个方向， 把路线压栈，走不通的时候回退路线接着找。
    对已经走过的路进行标记。
    # 回溯算法， 通过栈来实现
"""


def maze_route(x1, y1, x2, y2, list_):
    stack = []
    point = (x1, y1)
    
    func = [
        lambda x,y: (x-1, y), # 向上
        lambda x, y: (x+1, y), # 向下
        lambda x, y: (x, y-1), # 向左
        lambda x, y: (x, y+1) # 向右 
    ]
    stack.append(point)
    # 标记起始位置为2已走过
    list_[1][1] = 2
    # 当stack 的为空说明没有结果
    while len(stack) > 0:
        now_point = stack[-1]
        if now_point[0] == x2 and now_point[1] == y2:
            print(stack)
            return True
        # 进行移动
        for fun in func:
            new_point = fun(stack[-1][0], stack[-1][1])
            if list_[new_point[0]][new_point[1]] == 0:
                stack.append(new_point)
                # 将当前点标记为已经走过
                list_[new_point[0]][new_point[1]] = 2
                break
        # 说明几个方向都移动不了
        else:
            # 将当前点从栈里边移除
            stack.pop()
    print("没有路")
         
list_ = [
            [1,1,1,1,1,1,1,1,1],
            [1,0,0,1,1,1,1,1,1],
            [1,0,0,1,0,1,1,1,1],
            [1,1,0,0,0,1,1,1,1],
            [1,1,1,0,0,1,1,1,1],
            [1,1,0,0,0,1,1,1,1],
            [1,1,1,1,0,0,1,1,1],
            [1,1,1,0,0,0,0,0,1],
            [1,1,1,1,1,1,1,1,1],
        ]
maze_route(1,1,7,7, list_)   
        